package com.wj.algorithm.lintcode;

public class P140 {

    public int fastPower(int a, int b, int n) {
        if(n == 0 || a == 1) {
            if(b > 1) {
                return 1;
            }
            return 0;
        }
        
        a = a % b;
        
        int size = 0;
        long rs = 1;
        long tempRs = 1;
        while(n > 0) {
            if(size == 0) {
                tempRs = a;
            } else {
                tempRs = tempRs * tempRs;
            }
            tempRs = tempRs % b;
            if((n & 1) == 1) {//1
                rs *= tempRs;
            }
            rs = rs % b;
            n = n >> 1;
            size ++;
        }
        return (int) (rs % b);
    }
    
    public static void main(String[] args) {
        System.out.println(new P140().fastPower(2, 2147483647, 2147483647));
        System.out.println(new P140().fastPower(3, 7, 5));
    }
}
